/**
 * 剑指 Offer 19. 正则表达式匹配
 * https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
 */

/**
 * @param {string} s
 * @param {string} p
 * @return {boolean}
 */
function isMatch(s, p) {
  const dp = new Array(s.length + 1);
  for (let i = 0; i <= s.length; i += 1) {
    dp[i] = new Array(p.length + 1).fill(false);
  }
  dp[0][0] = true;
  for (let j = 1; j <= p.length; j += 1) {
    if (p[j - 1] === '*' && dp[0][j - 2]) {
      dp[0][j] = true;
    }
  }
  for (let i = 1; i <= s.length; i += 1) {
    const charS = s[i - 1];
    for (let j = 1; j <= p.length; j += 1) {
      const charP = p[j - 1];
      if (charS === charP || charP === '.') {
        dp[i][j] = dp[i - 1][j - 1];
      } else if (charP === '*') {
        const charPPre = p[j - 2];
        if (charS === charPPre || charPPre === '.') {
          dp[i][j] = dp[i - 1][j - 2] || dp[i][j - 2] || dp[i - 1][j];
        } else {
          dp[i][j] = dp[i][j - 2];
        }
      }
    }
  }
  return dp[s.length][p.length];
}

console.log(isMatch('aa', 'a') === false);
console.log(isMatch('aa', 'a*') === true);
console.log(isMatch('ab', '.*') === true);
console.log(isMatch('aab', 'c*a*b') === true);
console.log(isMatch('mississippi', 'mis*is*p*.') === false);
